#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>

using namespace std;

// 进程结构体
struct Process {
    string name;         // 进程名称
    int arrival;         // 到达时间
    int burst;           // 运行时间
    int remaining;       // 剩余运行时间
    int queue_level;     // 当前所在队列级别(1-3)
    bool emergency;      // 是否为紧急进程
    int wait_time;       // 在当前队列中的等待时间
    int start_time;      // 开始执行时间
    int finish_time;     // 完成时间
    int turnaround;      // 周转时间
    
    // 构造函数
    Process(string n, int a, int b, bool e = false) 
        : name(n), arrival(a), burst(b), remaining(b), queue_level(1), 
          emergency(e), wait_time(0), start_time(-1), finish_time(-1) {}
};

// 多级反馈队列调度器
class MLFQScheduler {
private:
    vector<queue<Process>> ready_queues;  // 3级就绪队列
    vector<int> time_slices;              // 各级队列的时间片
    int waiting_threshold;                // 等待阈值
    
public:
    MLFQScheduler() {
        // 初始化3个队列
        ready_queues.resize(3);
        
        // 设置各级队列的时间片：4、8、16
        time_slices = {4, 8, 16};
        
        // 设置等待阈值
        waiting_threshold = 32;
    }
    
    void schedule(vector<Process> processes) {
        int current_time = 0;
        int completed = 0;
        vector<Process> result_processes = processes;
        Process* current_process = nullptr;
        int current_slice = 0;
        
        // 排序进程，按到达时间排序
        sort(processes.begin(), processes.end(), 
            [](const Process& a, const Process& b) { 
                if (a.arrival == b.arrival) {
                    return a.emergency && !b.emergency;
                }
                return a.arrival < b.arrival; 
            });
        
        cout << "开始MLFQ调度算法模拟...\n";
        cout << "--------------------------------------------------------------------------------\n";
        
        while (completed < processes.size()) {
            // 检查是否有新进程到达
            for (auto& proc : processes) {
                if (proc.arrival == current_time) {
                    cout << "时间 " << current_time << ": 进程 " << proc.name 
                         << " 到达" << (proc.emergency ? "(紧急)" : "") << endl;
                    
                    // 紧急进程立即抢占
                    if (proc.emergency && current_process != nullptr) {
                        cout << "时间 " << current_time << ": 紧急进程 " << proc.name 
                             << " 抢占进程 " << current_process->name << endl;
                        
                        // 被抢占进程回到原队列队尾
                        ready_queues[current_process->queue_level - 1].push(*current_process);
                        
                        // 紧急进程立即执行
                        current_process = nullptr;
                    }
                    
                    // 新进程进入最高优先级队列
                    ready_queues[0].push(proc);
                }
            }
            
            // 优先级提升：检查低优先级队列中等待超时的进程
            for (int i = 1; i < ready_queues.size(); i++) {
                int size = ready_queues[i].size();
                for (int j = 0; j < size; j++) {
                    Process proc = ready_queues[i].front();
                    ready_queues[i].pop();
                    
                    proc.wait_time++;
                    
                    if (proc.wait_time >= waiting_threshold) {
                        cout << "时间 " << current_time << ": 进程 " << proc.name 
                             << " 等待超过阈值，从队列 " << (i+1) << " 提升至队列 " << i << endl;
                        
                        proc.queue_level = i;  // 提升优先级
                        proc.wait_time = 0;    // 重置等待时间
                        ready_queues[i-1].push(proc);
                    } else {
                        ready_queues[i].push(proc);
                    }
                }
            }
            
            // 检查当前进程是否已完成
            if (current_process != nullptr && current_process->remaining <= 0) {
                cout << "时间 " << current_time << ": 进程 " << current_process->name 
                     << " 完成" << endl;
                
                // 更新进程完成信息
                for (auto& proc : result_processes) {
                    if (proc.name == current_process->name) {
                        proc.finish_time = current_time;
                        proc.turnaround = proc.finish_time - proc.arrival;
                        break;
                    }
                }
                
                current_process = nullptr;
                current_slice = 0;
                completed++;
            }
            
            // 检查当前进程时间片是否用完
            if (current_process != nullptr && 
                current_slice >= time_slices[current_process->queue_level - 1]) {
                
                cout << "时间 " << current_time << ": 进程 " << current_process->name 
                     << " 时间片用完，从队列 " << current_process->queue_level 
                     << " 降级至队列 ";
                
                // 降级
                if (current_process->queue_level < 3) {
                    current_process->queue_level++;
                }
                
                cout << current_process->queue_level << endl;
                
                current_process->wait_time = 0;  // 重置等待时间
                ready_queues[current_process->queue_level - 1].push(*current_process);
                current_process = nullptr;
                current_slice = 0;
            }
            
            // 如果当前没有进程执行，从队列中选择一个
            if (current_process == nullptr) {
                // 优先从高优先级队列选择
                for (int i = 0; i < ready_queues.size(); i++) {
                    if (!ready_queues[i].empty()) {
                        Process proc = ready_queues[i].front();
                        ready_queues[i].pop();
                        
                        current_process = new Process(proc);
                        current_slice = 0;
                        
                        // 记录首次执行时间
                        for (auto& p : result_processes) {
                            if (p.name == current_process->name && p.start_time == -1) {
                                p.start_time = current_time;
                                break;
                            }
                        }
                        
                        cout << "时间 " << current_time << ": 进程 " << current_process->name 
                             << " 开始在队列 " << current_process->queue_level << " 执行" << endl;
                        
                        break;
                    }
                }
            }
            
            // 运行当前进程一个时间单位
            if (current_process != nullptr) {
                current_process->remaining--;
                current_slice++;
            } else {
                // CPU空闲
                cout << "时间 " << current_time << ": CPU空闲" << endl;
            }
            
            // 更新等待中进程的等待时间
            for (int i = 0; i < ready_queues.size(); i++) {
                int size = ready_queues[i].size();
                for (int j = 0; j < size; j++) {
                    Process proc = ready_queues[i].front();
                    ready_queues[i].pop();
                    proc.wait_time++;
                    ready_queues[i].push(proc);
                }
            }
            
            current_time++;
            cout << "--------------------------------------------------------------------------------\n";
        }
        
        // 输出结果
        print_results(result_processes);
    }
    
    void print_results(const vector<Process>& processes) {
        cout << "\n调度结果:\n";
        cout << "进程\t到达时间\t运行时间\t开始时间\t完成时间\t周转时间\n";
        
        double total_turnaround = 0;
        
        for (const auto& proc : processes) {
            cout << proc.name << "\t" 
                 << proc.arrival << "\t\t" 
                 << proc.burst << "\t\t" 
                 << proc.start_time << "\t\t"
                 << proc.finish_time << "\t\t" 
                 << proc.turnaround << "\n";
                 
            total_turnaround += proc.turnaround;
        }
        
        cout << "\n平均周转时间: " << fixed << setprecision(2) 
             << (total_turnaround / processes.size()) << endl;
    }
};

int main() {
    // 创建进程列表
    vector<Process> processes = {
        Process("A", 0, 12),
        Process("B", 2, 8),
        Process("C", 5, 32),
        Process("D", 6, 3, true),  // 紧急进程
        Process("E", 8, 21),
        Process("F", 9, 34),
        Process("G", 10, 7, true), // 紧急进程
        Process("H", 12, 22),
        Process("I", 15, 10)
    };
    
    // 创建调度器并开始调度
    MLFQScheduler scheduler;
    scheduler.schedule(processes);
    
    return 0;
}